#include "Interpreter.hpp"
#include <stack>
#include <algorithm>
using std::stack;

static int singleBraceExpansion(vector<string> &tokens, int tokenIndex);
static bool isBraceExpansion(const TaggedString &braceStr);
static void expandBraceContent(const TaggedString &braceStr, vector<string> &vec);

/// Performs brace expansion on a tokenized string. Any tokens of the form
/// PREFIX{braceExpr}SUFFIX will be replaced with multiple tokens, depending on
/// braceExpr.
void braceExpansion(vector<string> &tokens)
{
	for(size_t ii=0; ii<tokens.size(); )
	{
		int newTokens = singleBraceExpansion(tokens, ii);
		if(newTokens==1)
			ii++;
	}
}

string braceExpansion(const string &str)
{
	vector<string> tokens;
	separateArgs(tokens, str.c_str());
	
	braceExpansion(tokens);
	
	string ret = "";
	for(size_t ii=0; ii<tokens.size(); ii++)
	{
		if(ii>0) ret += " ";
		ret += tokens[ii];
	}
	return ret;
}

/// Performs brace expansion on the tokenIndex'th token in tokens. If expansion
/// was done, replaces the expanded token in the vector with several tokens,
/// and returns the number of tokens produced this way. If no change was made,
/// tokens is unchanged and returns 1 (the token is expanded to itself). Note
/// that just because an expansion was done, doesn't mean that no further
/// expansion is possible; to get the fully expanded result, you have to keep
/// calling this until it returns 1 on every token.
static int singleBraceExpansion(vector<string> &tokens, int tokenIndex)
{
	TaggedString str = tokens[tokenIndex];
	
	// Find all matched pairs of curly braces
	vector< pair<int,int> > curlyPairs;
	stack<int> unclosedCurlies;
	
	for(size_t ii=0; ii<str.length(); ii++)
	{
		if(str.isQuoted(ii) || str.isEscaped(ii))
			continue;
		
		if(str[ii]=='{') {
			// Exclude curlies preceded by a '$' (to avoid conflicting with
			// ${VAR})
			if(ii>0 && str[ii-1]=='$')
				continue;
			
			unclosedCurlies.push(ii);
		} else if(str[ii]=='}') {
			if(unclosedCurlies.size() > 0) {
				curlyPairs.push_back(pair<int,int>(unclosedCurlies.top(), ii));
				unclosedCurlies.pop();
			}
		}
	}
	
	// If no matched curly pairs, we're done
	if(!curlyPairs.size())
		return 1;
	
	// Sort curly-brace pairs by position of the opening curly
	sort(curlyPairs.begin(), curlyPairs.end());
	
	// Try each curly-pair in order, until we find one that's eligible for
	// expansion. (It's ineligible if its content has no unquoted commas and
	// isn't a range expressoin).
	for(size_t ii=0; ii<curlyPairs.size(); ii++)
	{
		int start = curlyPairs[ii].first;
		int end = curlyPairs[ii].second;
		TaggedString content = str.substr(start+1, end-start-1);
		trace << "content="<<content<<"\n"; //DEBUG
		if(isBraceExpansion(content))
		{
			vector<string> vec;
			expandBraceContent(content, vec);
			
			string prefix = str.substr(0, start);
			string suffix = str.substr(end+1, str.length()-end-1);
			
			for(size_t ii=0; ii<vec.size(); ii++)
				vec[ii] = prefix+vec[ii]+suffix;
			
			tokens.erase(tokens.begin()+tokenIndex);
			tokens.insert(tokens.begin()+tokenIndex, vec.begin(), vec.end());
			
			return vec.size();
		}
	}
	
	// There were curly pairs, but none of them were brace expansions
	return 1;
}

static bool isNumberRangeExpansion(const TaggedString &braceStr)
{
	for(size_t ii=0; ii<braceStr.size(); ii++)
	{
		if(braceStr.isQuoted(ii) || braceStr.isEscaped(ii))
			continue;
		
		// Found the dot
		if(braceStr[ii]=='.' && ii+2<braceStr.size() && braceStr[ii+1]=='.')
		{
			// Integers?
			return(stringIsInt(braceStr.substr(0, ii))
			    && stringIsInt(braceStr.substr(ii+2, braceStr.length()-ii-2)));
		}
	}
	
	return false;
}

static bool isCharacterRangeExpansion(const TaggedString braceStr)
{
	if(braceStr.length() != 4)
		return false;
	
	char start = braceStr[0];
	char end = braceStr[3];
	
	return ((start>='a' && start<='z') || (start>='A' && start<='Z'))
	    && ((end  >='a' && end  <='z') || (end  >='A' && end  <='Z'));
}

static bool isCommaExpansion(const TaggedString &braceStr)
{
	for(size_t ii=0; ii<braceStr.size(); ii++)
	{
		if(braceStr.isQuoted(ii) || braceStr.isEscaped(ii))
			continue;
		
		if(braceStr[ii]==',')
			return true;
	}
	
	return false;
}

static bool isBraceExpansion(const TaggedString &braceStr)
{
	return isNumberRangeExpansion(braceStr)
	    || isCharacterRangeExpansion(braceStr)
	    || isCommaExpansion(braceStr);
}

static void expandBraceContent(const TaggedString &braceStr, vector<string> &vec)
{
	if(isNumberRangeExpansion(braceStr))
	{
		// braceStr is of the form "123..321"
		// Find the '..'
		size_t ii;
		for(ii=0; ii<braceStr.size(); ii++) {
			if(braceStr[ii]=='.')
				break;
		}
		
		string startStr = braceStr.substr(0, ii);
		string endStr = braceStr.substr(ii+2, braceStr.length()-ii-2);
		int start = atoi(startStr.c_str());
		int end = atoi(endStr.c_str());
		
		char buf[32];
		if(start <= end)
		{
			for(int ii=start; ii<=end; ii++) {
				sprintf(buf, "%i", ii);
				vec.push_back(buf);
			}
		} else {
			for(int ii=start; ii>=end; ii--) {
				sprintf(buf, "%i", ii);
				vec.push_back(buf);
			}
		}
	}
	else if(isCharacterRangeExpansion(braceStr))
	{
		// braceStr is of the form "C..C"
		char start = braceStr[0];
		char end = braceStr[3];
		char str[2] = {0,0};
		
		if(start<=end)
		{
			for(int ii=start; ii<=end; ii++) {
				str[0] = ii;
				vec.push_back(str);
			}
		}
		else
		{
			for(int ii=start; ii>=end; ii--) {
				str[0] = ii;
				vec.push_back(str);
			}
		}
	}
	else if(isCommaExpansion(braceStr))
	{
		int start = 0;
		int nestLevel = 0;
		for(size_t ii=0; ii<braceStr.length(); ii++)
		{
			if(braceStr.isQuoted(ii) || braceStr.isEscaped(ii))
				continue;
			
			if(braceStr[ii]=='{')
				nestLevel++;
			else if(braceStr[ii]=='}')
				nestLevel--;
			else if(braceStr[ii]==',' && !nestLevel)
			{
				vec.push_back(braceStr.substr(start, ii-start));
				start = ii+1;
			}
		}
		vec.push_back(braceStr.substr(start, braceStr.length()-start));
	}
	
}

TEST_SET(braceExpansion)
{
	testAssert(braceExpansion("a{b,c,d}e") == "abe ace ade");
	testAssert(braceExpansion("{a,b}{c,d}{e,{f,g}}") == "ace acf acg ade adf adg bce bcf bcg bde bdf bdg");
	testAssert(braceExpansion("a{1..5}") == "a1 a2 a3 a4 a5");
	testAssert(braceExpansion("a{5..1}") == "a5 a4 a3 a2 a1");
	testAssert(braceExpansion("a {1..5}") == "a 1 2 3 4 5");
	testAssert(braceExpansion("{a..f}") == "a b c d e f");
	testAssert(braceExpansion("{F..A}") == "F E D C B A");
}

